#define _CRT_SECURE_NO_WARNINGS -1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

void Swap(int* x1, int* x2)
{
	assert(x1 && x2);
	int tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;
}
void moveZeroes(int* nums, int numsSize)
{
	assert(nums);
	int pre = 0;
	int cur = 0;
	while (cur < numsSize)
	{
		if (nums[pre] == 0)
		{
			if (nums[cur] != 0)
			{
				Swap(nums + pre, nums + cur);
			}
			else
			{
				cur++;
				continue;
			}
		}
		pre++;
		cur++;
	}
}


//int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) 
//{
//	assert(numbers);
//	*returnSize = 2;
//	int* result = (int*)malloc(sizeof(int) * 2);
//	assert(result);
//	int left = 1;
//	int right = 0;
//	
//	if (target < 0)
//	{
//		left = 1;
//		while (left <= numbersSize && numbers[left - 1] <= 0)
//			left++;
//	}
//	else
//	{
//		while (left <= numbersSize && numbers[left - 1] <= target)
//			left++;
//		left--;
//	}
//
//	while (left >= 1)
//	{
//		if(left < numbersSize && numbers[left - 1] + numbers[left] <= target && numbers[left - 1] + numbers[numbersSize - 1] >= target)
//		{
//			while (left >= 1)
//			{
//				right = left + 1;
//				while (right <= numbersSize)
//				{
//					if (numbers[left - 1] + numbers[right - 1] == target)
//					{
//						result[0] = left;
//						result[1] = right;
//						return result;
//					}
//					right++;
//				}
//				left--;
//			}
//			break;
//		}
//		left--;
//	}
//	return NULL;
//}


//int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
//	int* ret = (int*)malloc(sizeof(int) * 2);
//	*returnSize = 2;
//
//	for (int i = 0; i < numbersSize; ++i) {
//		int low = i + 1, high = numbersSize - 1;
//		while (low <= high) {
//			int mid = (high - low) / 2 + low;
//			if (numbers[mid] == target - numbers[i]) {
//				ret[0] = i + 1, ret[1] = mid + 1;
//				return ret;
//			}
//			else if (numbers[mid] > target - numbers[i]) {
//				high = mid - 1;
//			}
//			else {
//				low = mid + 1;
//			}
//		}
//	}
//	ret[0] = -1, ret[1] = -1;
//	return ret;
//}

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
{
	assert(numbers);
	int* result = (int*)malloc(sizeof(int) * 2);
	assert(result);
	int left = 0;
	int right = numbersSize - 1;
	while (left < right)
	{
		if (numbers[left] + numbers[right] == target)
			break;
		else if (numbers[left] + numbers[right] > target)
			right--;
		else
			left++;
	}
	result[0] = left + 1;
	result[1] = right + 1;
	return result;
}

int main()
{
	int nums[] = { 2,7,11,15 };
	int j = 0;
	int* a = twoSum(nums, sizeof(nums) / sizeof(nums[0]), 9, &j);
	for (int i = 0; i < 2; i++)
		printf("%d ", a[i]);
	return 0;
}